package dataStructure.study.linkedList;

/**
 * Author: shangsf
 * Date: 2021/3/28 14:46
 * Description:单链表
 */
public class SingleLinkedList<T> {
    private Node<T> head=null;
    private int size;


    public void addFirst(T data){
        Node<T> newNode=new Node<T>(data);
        if(head==null){
            head=newNode;
        }else {
            newNode.next=head;
            head=newNode;
        }
        size++;
    }

    public void addLast(T data){
        Node<T> newNode=new Node<T>(data);
        if(head==null){
            head=newNode;
        }else {
            Node<T> temp=head;
            while (temp.next!=null){
                temp=temp.next;
            }
            temp.next=newNode;
        }
        size++;
    }

    public void add(T data){
        addLast(data);
    }

    public void remove(T data){
        if(null==data){
            return;
        }
        Node<T> prev=null;
        Node<T> temp=head;
        if(null==temp){
            return;
        }
        for(;temp!=null;temp=temp.next){
            if(temp.data.equals(data)){
                if(prev==null){//头节点
                    head=head.next;
                }else {
                    prev.next=temp.next;
                }
                --size;
                break;
            }
            prev=temp;
        }
    }

    public T remove(){
        if(head==null){
            return null;
        }
        Node<T> node=head;
        head=head.next;
        size--;
        return node.data;
    }

    public T getFirst(){
        return head!=null?head.data:null;
    }

    public T getLast(){
        if(head==null){
            return null;
        }
        Node<T> node = head;
        while (node.next!=null){
            node=node.next;
        }
        return node.data;
    }

    public T get(int index){
        if(index>=size){
            return null;
        }
        int count=0;
        Node<T> node=head;
        if(node==null){
            return null;
        }
        if(count==index){
            return node.data;
        }
        while (node.next!=null){
            count++;
            node=node.next;
            if(count==index){
                return node.data;
            }
        }
        return null;
    }

    public int size(){
        return size;
    }

    /**
     * 反转
     */
    public void reverse(){
        if(size==0){
            return;
        }
        Node<T> prev=null;
        Node<T> curr=head;
        Node<T> next=head.next;
        while (next!=null){
            if(prev==null){
                curr.next=null;
            }
            prev=curr;
            curr=next;
            next=next.next;

            curr.next=prev;
        }
        head=curr;
    }

    /**
     * 反转1：递归反转
     */
    public void reverse1(){
        head= reverse_recursion(head);
    }

    Node<T> reverse_recursion(Node<T> node){
        // node是前一结点，node.next是当前结点，newNode是反转后新链表的头结点
        if(node==null||node.next==null){
            return node;//若为空链或者当前结点在尾结点，则直接还回
        }
        Node<T> newNode=reverse_recursion(node.next);//先反转后续节点node.next

        node.next.next=node;//将当前结点的指针域指向前一结点
        node.next=null;//前一结点的指针域令为null

        return newNode;
    }


    public static class Node<T>{
        public T data;
        public Node<T> next;

        public Node(T t){
            data=t;
            next=null;
        }
    }
}
